Conventional cache algorithms maintain coherence at the granularity of cache blocks. However, as cache sizes have become larger, the efficacy of these cache algorithms has decreased. Inefficiencies have been created both by storing information and data block by block, and by accessing and controlling on the block level.
Solutions for this decreased efficacy have included attempts to provide macro-level cache policies by exploiting coherence information of larger regions. These larger regions may include a contiguous set of cache blocks in physical address space, for example. These solutions have allowed for the storage of control information at the region level instead of storing control information on a block by block basis, thereby decreasing the storage and access necessary for the control information.
These attempts have been made to opportunistically maintain coherence at a granularity larger than a block size—typically 64 bytes. These attempts are designed to save unnecessary bandwidth, for example. Specifically, these attempts either incorporate additional structures that track coherence across multiple cache block sized regions or merge both region and individual cache block information into a single structure. When the region-level information indicates that no other caches cache a particular region, the snoops associated with certain requests may be deemed unnecessary, thus saving bandwidth.
For example, region coherence may be extended, such as using Virtual Tree Coherence, in a hybrid directory/snooping protocol where the directory assigned regions to multicast trees. Requests may be utilized within the tree to maintain coherence. Specifically, Virtual Tree Coherence may utilize region tracking structure and only track sharing information at the region level. Thus cache blocks within shared regions may not be assigned individual owners, and marked sharers for a region level must respond to all requests with that region.
The problem with these previous attempts is a failure to achieve the proper balance between storage overhead and bandwidth demand because these attempts only track sharing information at one level of granularity; either block or region. Therefore, there is a need to balance storage overhead and bandwidth demand by tracking sharing information at both block and region granularities.